package com.ErChaShu;

/**
 *
 */
public class 二叉查找树 {

    public Node root;

    private class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    public void printNode(Node root) {
        if (root.left != null) {
            printNode(root.left);
        }
        if (root.right != null) {
            printNode(root.right);
        }
        System.out.println(root.data);
    }

    public static void main(String[] args) {
        二叉查找树 er = new 二叉查找树();
        er.insert(3);
        er.insert(2);
        er.insert(4);
        Node search = er.search(4);
        er.printNode(er.root);
    }

    public Node search(int data) {
        Node targetNode = root;
        while (targetNode != null) {
            if (data > targetNode.data) {
                targetNode = targetNode.right;
            } else if (data == targetNode.data) {
                break;
            } else {
                targetNode = targetNode.left;
            }
        }
        if (targetNode == null) {
            System.out.println("未找到");
        } else {
            System.out.println("找到值的节点");
        }
        return targetNode;
    }

    public boolean insert(int data) {
        Node node = new Node(data);
        if (root == null) {
            root = node;
            return true;
        }

        Node targetNode = root;
        while (targetNode != null) {
            if (targetNode.data == data) {
                return false;
            } else if (data > targetNode.data) {
                if (targetNode.right == null) {
                    targetNode.right = node;
                    return true;
                }
                targetNode = targetNode.right;
            } else {
                if (targetNode.left == null) {
                    targetNode.left = node;
                    return true;
                }
                targetNode = targetNode.left;
            }
        }
        return true;
    }

}
